package com.algorithm.base.backtracking;

import java.util.*;

/**
 * 组合sum2
 *
 * @author Amadeus
 * @date 2023/11/02
 */
public class CombinationSum2 {

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();
        Deque<Integer> deque = new ArrayDeque<>();
        Arrays.sort(candidates);
        int[] nums = new int[candidates.length + 1];
        backTrackingPruning(target, candidates, result, deque, 0, nums);
        return result;
    }

    public void backTrackingPruning(int target, int[] candidates, List<List<Integer>> result,
                                    Deque<Integer> deque, int index, int[] nums) {
        if (target == 0) {
            result.add(new ArrayList<>(deque));
            return;
        }
        if (target < 0) {
            return;
        }
        for (int i = index; i < candidates.length; i++) {
            if (target < candidates[i]) {
                break;
            }
            if (i > 0 && candidates[i] == candidates[i - 1] && nums[i - 1] == 0) {
                continue;
            }
            target -= candidates[i];
            deque.addLast(candidates[i]);
            nums[i] = 1;
            backTrackingPruning(target, candidates, result, deque, i + 1, nums);
            target += candidates[i];
            nums[i] = 0;
            deque.removeLast();
        }
    }
}